"""
@author: wy
@file: 15.py
@time: 2023/12/7 19:07
"""
#15、有一个n阶台阶，一个人可以一次走一步或者走两步，问要想走上去有多少种方式？
def max_way(n):
    if n==1:
        return 1
    if n==2:
        return 2
    return max_way(n-1)+max_way(n-2)
n=max_way(4)
print(n)
# 1 11 11
# 1 2 2
# 2 1 2
# 2 2 1
# 1 1 1 2
# 1 1 2 1
# 1 2 1 1
# 2 1 1 1
def climbStairs(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

x=climbStairs(4)
print(x)